package SwordFingerOffer;

public class Q13_RobotRange {
    //机器人运动范围

    public static int movingCount(int m, int n, int k) {

        if (m < 0 || n < 0 || k < 0){
            return 0;
        }
        //是否到达过
        boolean[][] used = new boolean[m][n];
        return process(m, n, k, 0, 0, used);

    }

    //重新整合题目条件的重要性 ！！
    //重新整合题目条件  ==> 一个点错 其右和下皆是错 ==> 可达解区域连续！！ ==> 把每个点右边和左边能拿的格子都拿到 ==> 发现我们的递归并不需要向上和向左走
    //与前面不同的是：
    //1. 每个格子只需要走一遍 不需要其他递归参与了 所以不需要恢复现场
    private static int process(int m, int n, int k, int row, int col, boolean[][] used) {

        if (get(row) + get(col) > k || row == m || col == n || used[row][col])
        return 0;
        //base case
//        if (row == m - 1 && col == n - 1)
//        return 1;
        //向下
        int down = process(m,n,k,row + 1, col, used);
        //向右
        int right = process(m,n,k,row, col + 1, used);
        used[row][col] = true;
        return down + right + 1;
    }
    //计算数位和
    private static int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(movingCount(3, 2, 17));
    }
}
